package algorithm;

import java.util.*;

public class Leetcode451 {
    public String frequencySort(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int length = s.length();
        for (int i = 0;i < length; i++) {
            int count = map.getOrDefault(s.charAt(i), 0);
            map.put(s.charAt(i), count+1);
        }

        List<Character> list = new ArrayList<>(map.keySet());
        Collections.sort(list, new Comparator<Character>() {
            @Override
            public int compare(Character o1, Character o2) {
                return map.get(o2) - map.get(o1);
            }
        });
        StringBuffer stringBuffer = new StringBuffer();
        int size = list.size();
        for (int i = 0;i < size;i++) {
            char ch = list.get(i);
            int count = map.get(ch);
            for (int j = 0;j < count; j++) {
                stringBuffer.append(ch);
            }
        }
        return stringBuffer.toString();
    }
}
